{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Ungraded Lab - Gradient for regularized logistic regression\n",
    "In this lab you will extend the implementation of determining the gradient to include regularization."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [],
   "source": [
    "import numpy as np\n",
    "from lab_utils import sigmoid"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Gradient for regularized logistic regression\n",
    "\n",
    "Below, you will implement the gradient for regularized logistic regression.\n",
    "\n",
    "The gradient of the regularized cost function is a vector with the same shape as the parameters $\\mathbf{w}$, where the $j^\\mathrm{th}$ element is defined as follows:\n",
    "\n",
    "$$\\frac{\\partial J(\\mathbf{w})}{\\partial w_0} = \\frac{1}{m}  \\sum_{i=0}^{m-1} (f_{\\mathbf{w}}(\\mathbf{x}^{(i)}) - y^{(i)}) x_j^{(i)} \\quad\\quad\\quad\\quad\\quad\\quad \\mbox{for $j = 0$}$$\n",
    "\n",
    "$$\\frac{\\partial J(\\mathbf{w})}{\\partial w_j} = \\left( \\frac{1}{m}  \\sum_{i=0}^{m-1} (f_{\\mathbf{w}}(\\mathbf{x}^{(i)}) - y^{(i)}) x_j^{(i)} \\right) + \\frac{\\lambda}{m} w_j  \\quad\\, \\mbox{for $j \\geq 1$}$$\n",
    "\n",
    "\n",
    "You'll implement a function called `compute_gradient_reg` which will return $\\frac{\\partial J(\\mathbf{w})}{\\partial \\mathbf{w}}$.\n",
    "\n",
    "In the instructions and code below, the term 'dw' refers to $\\frac{\\partial J(\\mathbf{w})}{\\partial \\mathbf{w}}$. The dJ is implied.  \n",
    "Please complete the `compute_gradient_reg` function to:\n",
    "- Loop over each element in dw (which has been initialized to 0) (`j`). \n",
    "    - Calculate the gradient for each element ($dw_j$) \n",
    "        - Loop over all examples in the training set. Create a variable outside the loop to store the total gradient\n",
    "        - Inside the loop, calculate the gradient update from each training example \n",
    "            - Calculate `z`\n",
    "            $$\n",
    "            z =  w_0x_0^{(i)} + w_1x_1^{(i)} + w_2x_2^{(i)} = \\mathbf{w} \\cdot \\mathbf{x}^{(i)}\n",
    "            $$\n",
    "            - Predict `f` where `g` is the sigmoid function\n",
    "            $$\n",
    "            f =  g(z)\n",
    "            $$\n",
    "            - Calculate the gradient from each example\n",
    "\n",
    "            $$gradient =  (f - y^{(i)})x_j^{(i)}$$\n",
    "    \n",
    "            - Add this gradient to the total gradient variable created outside the loop\n",
    "    \n",
    "        - Get the total gradient at $dw_j$ as the sum of the gradient from all iterations and return the total divided by the number of examples.\n",
    "    - If `j> 0`\n",
    "        - add $\\frac{\\lambda}{m} w_j$ to $dw_j$\n",
    "\n",
    "As you are doing this, remember that the variables X and y are not scalar values but matrices of shape ($m, n+1$) and ($𝑚$, ) respectively, where  $𝑛$ is the number of features and $𝑚$ is the number of training examples. \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [],
   "source": [
    "## GRADED FUNCTION: compute_gradient_reg\n",
    "\n",
    "def compute_gradient_reg(X, y, w, lambda_=1): \n",
    "    \"\"\"\n",
    "    Computes the gradient for regularized logistic regression.\n",
    "    \n",
    "    Parameters\n",
    "    ----------\n",
    "    X : array_like\n",
    "        Shape (m, n+1) \n",
    "    \n",
    "    y : array_like\n",
    "        Shape (m,) \n",
    "    \n",
    "    w : array_like\n",
    "        Parameters of the model\n",
    "        Shape (n+1,)\n",
    "        \n",
    "    lambda_ : float\n",
    "        Controls amount of regularization\n",
    "        Default is set to 1\n",
    "    \n",
    "    Returns\n",
    "    -------\n",
    "    dw : array_like\n",
    "        Shape (n+1,)\n",
    "        The gradient of the regularized cost w.r.t. the parameters w. \n",
    "        Note that dw has the same dimensions as w.\n",
    "    \"\"\"\n",
    "    \n",
    "    m, n = X.shape\n",
    "    \n",
    "    # You will need to replace/update dw\n",
    "    dw = np.zeros_like(w)\n",
    "    \n",
    "    ### START CODE HERE ### \n",
    "    ### BEGIN SOLUTION ###\n",
    "    for j in range(n):\n",
    "        gradient_list = []\n",
    "        \n",
    "        for i in range(m):        \n",
    "            z = np.dot(w.T, X[i])\n",
    "            f = sigmoid(z)\n",
    "            gradient = (f-y[i])*X[i][j]          \n",
    "            gradient_list.append(gradient)\n",
    "        \n",
    "        dw[j] = (1/m)* sum(gradient_list)\n",
    "        \n",
    "        if j > 0:\n",
    "            dw[j] += (lambda_/m)*w[j]\n",
    "    ### END SOLUTION ###  \n",
    "    ### END CODE HERE ### \n",
    "    \n",
    "    return dw"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Run the cell below to check your implementation of the `compute_gradient_reg` function."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "First few elements of regularized gradient:\n",
      " [ 0.09181613  0.14678723 -0.00790065 -0.03773603]\n"
     ]
    }
   ],
   "source": [
    "np.random.seed(1)\n",
    "X_tmp = np.random.rand(5,6)\n",
    "y_tmp = np.array([0,1,0,1,0])\n",
    "initial_w = np.random.rand(X_tmp.shape[1]) - 0.5\n",
    "lambda_ = 1\n",
    "grad = compute_gradient_reg(X_tmp, y_tmp, initial_w, lambda_)\n",
    "\n",
    "print(f\"First few elements of regularized gradient:\\n {grad[:4]}\", )"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Expected Output**:\n",
    "<table>\n",
    "  <tr>\n",
    "    <td> <b>First few elements of regularized gradient:</b </td></tr>\n",
    "    <td>  [ 0.09181613  0.14678723 -0.00790065 -0.03773603] </td> \n",
    "  </tr>\n",
    "</table>"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.8.6"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 5
}
